package com.example.algorithm.service.impl;

import com.example.algorithm.service.CleverService;
import org.springframework.stereotype.Service;

import java.lang.reflect.Array;
import java.util.*;

/**
 * @auth Administrator
 * @create @2024/8/14@21:16
 * @decription
 **/
@Service
public class CleverServiceImpl implements CleverService {
    /**NO.96 只出现一次的数字
     * 给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
     *
     * 你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
     * @param nums
     * @return
     */
    /**
     * 解法一：位运算
     * 数组中的全部元素的异或运算结果即为数组中只出现一次的数字。
     * 时间复杂度：O(n)，其中 n 是数组长度。只需要对数组遍历一次。
     * 空间复杂度：O(1)。
     * @param nums
     * @return
     */
    @Override
    public int singleNumber(int[] nums){
         int single=0;
         for(int num:nums){
             single =single^num;
         }
         return single;
    }

    /**
     * 解法二：栈
     * 数组中的全部元素的异或运算结果即为数组中只出现一次的数字。
     * 时间复杂度：O(n)，其中 n 是数组长度。只需要对数组遍历一次。
     * 空间复杂度：O(1)。
     * @param nums
     * @return
     */
    public int singleNumber1(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int num:nums){
          if(!set.add(num)){
              set.remove(num);
          }
        }
        return set.iterator().next().intValue();
    }

    /**NO.97 多数元素
     * 给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

     你可以假设数组是非空的，并且给定的数组总是存在多数元素。
     *
     * @param nums
     * @return
     */
    /**
     * 解法一哈希表
     * 思路：
     * 我们知道出现次数最多的元素大于 n/2次，所以可以用哈希表来快速统计每个元素出现的次数。
     * 时间复杂度：O(n)。
     * 空间复杂度：O(n)，其中 n 是数组 nums 的长度。
     * @param nums
     * @return
     */
    @Override
    public int majorityElement(int[] nums) {
       Map<Integer,Integer> res = new HashMap<>();
       for(int num:nums){
           if(res.containsKey(num)){
               res.put(num,res.get(num));
           }
           res.put(num,1);
       }
       Map.Entry<Integer,Integer> max=null;
       for(Map.Entry<Integer,Integer> tmp:res.entrySet()){
           if(max==null||max.getValue()<=tmp.getValue()){
               max = tmp;
           }
       }
       return max.getKey();
    }

    /**
     * 解法二 排序
     * 思路：
     如果将数组 nums 中的所有元素按照单调递增或单调递减的顺序排序，那么下标为 n/2
     的元素（下标从 0 开始）一定是众数。
     时间复杂度：O(nlogn)。将数组排序的时间复杂度为 O(nlogn)。

     空间复杂度：O(logn)。如果使用语言自带的排序算法，需要使用 O(logn) 的栈空间。如果自己编写堆排序，则只需要使用 O(1) 的额外空间。

     * @param nums
     * @return
     */
    public int majorityElement1(int[] nums) {
        Arrays.sort(nums);
        int len=nums.length;
        return nums[len/2];
    }
    /**
     * 解法三 Boyer-Moore 投票算法
     * 思路：
     如果我们把众数记为 +1，把其他数记为 −1，将它们全部加起来，显然和大于 0，从结果本身我们可以看出众数比其他数多。
     时间复杂度：O(n)。Boyer-Moore 算法只对数组进行了一次遍历。

     空间复杂度：O(1)。Boyer-Moore 算法只需要常数级别的额外空间。
     * @param nums
     * @return
     */
    public int majorityElement2(int[] nums){
        int count=0;
        int candidate=0;
        for(int num:nums){
            if(count==0){
                candidate=num;
            }
            count+=(candidate==num)?1:-1;
        }
        return candidate;
    }


    /**NO.98 颜色分类
     * 给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
     *
     * 我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
     *
     * 必须在不使用库内置的 sort 函数的情况下解决这个问题。
     * @param nums
     */
    @Override
    public void sortColors(int[] nums) {
        int num0=0,num1=0,num2=0;
        for(int num:nums){
            if(num==0){
                nums[num2++]=2;
                nums[num1++]=1;
                nums[num0++]=0;
            }else if(num==1){
                nums[num2++]=2;
                nums[num1++]=1;
            }else{
                nums[num2++]=2;
            }
        }
    }

    /**
     * 解法一：单指针
     * 思路：
     * 我们可以考虑对数组进行两次遍历。在第一次遍历中，我们将数组中所有的 0 交换到数组的头部。
     * 在第二次遍历中，我们将数组中所有的 1 交换到头部的 0 之后。此时，所有的 2 都出现在数组的尾部，
     * 这样我们就完成了排序。
     * 时间复杂度：O(1)。
     * 空间复杂度：O(n)，其中 n 是数组 nums 的长度。

     *
     * @param nums
     */
    public void sortColors1(int[] nums){
        int len = nums.length;
        int ptr = 0;
        for(int i=0;i<len;i++){
            if(nums[i]==0){
                int tmp = nums[i];
                nums[i]=nums[ptr];
                nums[ptr]=tmp;
                ptr++;
            }
        }
        for(int i=ptr;i<len;i++){
            if(nums[i]==1){
                int tmp = nums[i];
                nums[i]=nums[ptr];
                nums[ptr]=tmp;
                ptr++;
            }
        }

    }
    /**
     * 解法二：双指针
     * 思路：
     我们也可以考虑使用指针 p0
     来交换 0，p2来交换 2。此时，p0
     的初始值仍然为 0，而 p2
     的初始值为 n−1。在遍历的过程中，我们需要找出所有的 0 交换至数组的头部，
     并且找出所有的 2 交换至数组的尾部
     * 时间复杂度：O(1)。
     * 空间复杂度：O(n)，其中 n 是数组 nums 的长度。
     * @param nums
     */
    public void sortColors2(int[] nums){
        int len = nums.length;
        int left = 0,right=len-1;
        for(int i=0;i<=right;i++){
            while (i<=right&&nums[i]==2){
                 int tmp = nums[i];
                 nums[i]=nums[right];
                 nums[right]=tmp;
                 --right;
            }
            if(nums[i]==0){
                int tmp=nums[i];
                nums[i]=nums[left];
                nums[left]=tmp;
                ++left;
            }
        }
    }

    /**
     * 解法三：计数法
     * 思路：
     通过三个有包含关系的计数器，来分别动态算出0,1,2个数，并修改对应的值

     遍历数组： i：代表目前为止(0 + 1 + 2) 的数量

     n1: 代表目前为止 (0 + 1)的数量

     n0: 代表目前为止 (0)的数量
     * 时间复杂度：O(1)。
     * 空间复杂度：O(n)，其中 n 是数组 nums 的长度。
     * @param nums
     */
    public void sortColors3(int[] nums){
        int len = nums.length;
        int cnt0=0,cnt1=0;
        for(int i=0;i<len;i++){
            int tmp =  nums[i];
            nums[i]=2;
            if(tmp<2){
                nums[cnt1++]=1;
            }
            if(tmp<1){
                nums[cnt0++]=0;
            }
        }

    }




    /**NO.99 下一个排列
     * 整数数组的一个 排列  就是将其所有成员以序列或线性顺序排列。
     *
     * 例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
     * 整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
     *
     * 例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
     * 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
     * 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
     * 给你一个整数数组 nums ，找出 nums 的下一个排列。
     *
     * 必须 原地 修改，只允许使用额外常数空间。
     * @param nums
     */
    /**
     * 解法一：两编扫描
     * 注意到下一个排列总是比当前排列要大，除非该排列已经是最大的排列。我们希望找到一种方法，能够找到一个大于当前序列的新序列，且变大的幅度尽可能小。具体地：
     *
     * 我们需要将一个左边的「较小数」与一个右边的「较大数」交换，以能够让当前排列变大，从而得到下一个排列。
     *
     * 同时我们要让这个「较小数」尽量靠右，而「较大数」尽可能小。当交换完成后，「较大数」右边的数需要按照升序重新排列。这样可以在保证新排列大于原来排列的情况下，使变大的幅度尽可能小。
     * 时间复杂度：O(nlogn)
     * 空间复杂度：O(1)
     * @param nums
     * @return
     */

    @Override
    public void nextPermutation(int[] nums) {
        int len = nums.length;
        if(len<=1){
            return;
        }
        int i=len-2;
        while (i>=0&&nums[i]>=nums[i+1]){
            i--;
        }
        if(i>0){
           int j=len-1;
            while (j>=0&&nums[i]>=nums[j]){
                j--;
            }
            int temp = nums[i];
            nums[i]=nums[j];
            nums[j]=temp;
        }
        reverse(nums,i+1);

    }
    public void reverse(int[] nums, int start) {
        int left = start, right = nums.length - 1;
        while (left < right) {
            int temp = nums[left];
            nums[left]=nums[right];
            nums[right]=temp;
            left++;
            right--;
        }
    }

    /**NO.100 寻找重复数字
     * 给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
     *
     * 假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
     *
     * 你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
     * @param nums
     * @return
     *
     *
     */

    /**
     * 解法一：二分查找法
     * 时间复杂度：O(nlogn)
     * 空间复杂度：O(1)
     * @param nums
     * @return
     */
    public int findDuplicate1(int[] nums) {
       int left=0;
       int right=nums.length-1;
        //cnt[i] 表示 nums 数组中小于等于 i 的数有多少个
       int cnt=0;
       int rst=-1;
        while (left<=right){
            int mid = (left +right)>>2;
            for(int i=0;i<nums.length;i++){
                if(nums[i]<=mid){
                    cnt++;
                }
            }
            if(cnt<=mid){
                left=mid+1;
            }else{
                right=mid-1;
                rst=mid;
            }
        }
        return rst;
    }
    /**
     * 解法二：二进制
     * 思路：
     * 考虑第 i 位，我们记 nums 数组中二进制展开后第 i 位为 1 的数有 x 个，
     * 数字 [1,n] 这 n 个数二进制展开后第 i 位为 1 的数有 y 个，
     * 那么重复的数第 i 位为 1 当且仅当 x>y。
     * 时间复杂度：O(nlogn)
     * 空间复杂度：O(1)
     * @param nums
     * @return
     */
    public int findDuplicate2(int[] nums) {
        int len=nums.length;
        int bit_max=31;
        int ret=0;
        /**
         * 计算数组中数字的最大二进制长度
         */
        while ((len-1)>>bit_max==0){
            bit_max--;
        }
        for(int bit=0;bit<bit_max;bit++){
            int x=0,y=0;
            for(int i = 0; i < len; ++i){
                if((nums[i]&(1<<bit))!=0){
                  x++;
                }
                if(i>=1&&(i&(1<<bit))!=0){
                    y++;
                }
            }
            if(x>y){
                ret |=1<<bit;
            }

        }
        return ret;
    }
    /**
     * 解法三：快慢指针
     * 思路：
     我们对 nums 数组建图，每个位置 i 连一条 i→nums[i] 的边。由于存在的重复的数字 target，
     因此 target 这个位置一定有起码两条指向它的边，因此整张图一定存在环，
     且我们要找到的 target 就是这个环的入口，那么整个问题就等价于 142. 环形链表 II。
     我们先设置慢指针 slow 和快指针 fast ，慢指针每次走一步，快指针每次走两步，
     根据「Floyd 判圈算法」两个指针在有环的情况下一定会相遇，
     此时我们再将 slow 放置起点 0，两个指针每次同时移动一步，相遇的点就是答案。
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     * @param nums
     * @return
     */
    public int findDuplicate3(int[] nums){
        int slow=0,fast=0;
        // 快慢指针从起点出发，慢指针走一步，快指针走两步，它们最终相遇，则一定有环
        do{
            slow=nums[slow];
            fast=nums[nums[fast]];

        }while (slow!=fast);
        //慢指针从起点出发，快指针从上次相遇点出发，它们同时走一步，再次相遇点为环的入口
        slow=0;
        while (slow!=fast){
            slow=nums[slow];
            fast=nums[fast];
        }
        return slow;
    }
    /**
     * 解法四  ：启发式方法
     * 思路：
     在数组存在两个及以上的相同数字时，我们将数组中的数字放到与值相同的索引上，
     即i=nums[i]，一定会出现一个坑位超过一个数字的情况，因此我们就可以找到重复的数字了
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)
     * @param nums
     * @return
     */
    @Override
    public int findDuplicate(int[] nums) {
       int index=0, val=0;
       while (index!=nums[index]){
           val=nums[index];
           nums[index]=index;
           index=val;

       }
       return index;
    }

    /**
     * 解法五  ：哈希表
     * 思路：
     利用数据结构特点，容易想到使用哈希表（Set）记录数组的各个数字，当查找到重复数字则直接返回。
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)
     * @param nums
     * @return
     */
    public int findDuplicate4(int[] nums){
        HashSet<Integer> set = new HashSet();
        for(int num:nums){
            if(set.contains(num)){
               return num;
            }
            set.add(num);
        }
        return -1;
    }
    /**
     * 解法六  ：原地交换
     * 思路：
     遍历中，第一次遇到数字 x 时，将其交换至索引 x 处；而当第二次遇到数字 x 时，一定有 nums[x]=x ，此时即可得到一组重复数字。
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     * @param nums
     * @return
     */
    public int findDuplicate5(int[] nums){
        int i=0;
        while (i<nums.length){
            if(nums[i]==i){
                i++;
                continue;
            }
            if(nums[nums[i]]==nums[i]){
                return nums[i];
            }
            int tmp=nums[i];
            nums[i]=nums[tmp];
            nums[tmp]=tmp;

        }
        return -1;
    }


}
